package com.cat.graphTheory;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/ipo/description/
 * @create 2025/10/7 21:02
 * @since JDK17
 */

public class Solution39 {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i] = new int[]{profits[i], capital[i]};
        }
        Arrays.sort(arr, (a, b) -> a[1] - b[1]);    // 按照资本排序
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
        for (int i = 0, j = 0; i < k; i++) {
            while (j < n && w >= arr[j][1]) {   // 将可以投资的企业加入堆中
                heap.add(arr[j++][0]);
            }
            if (heap.isEmpty()) {
                break;
            }
            w += heap.poll();
        }

        return w;
    }
}
